#ifndef BST_H_INCLUDED
#define BST_H_INCLUDED

#include "dataline.h"
#include <fstream>


namespace STLData {

    class BNode {
        public:
        typedef struct {
            dataLine fields;
            std::string fileLine;
            int filenum;
        } Comparable;
        Comparable element;
        int level;
        BNode * link[2];

        BNode() {
            link[0] = NULL;
            link[1] = NULL;
            level = 1;
        }

        BNode( const Comparable & e, BNode *lt, BNode *rt, int lv = 1 ) {
            element.fields = e.fields;
            element.fileLine = e.fileLine;
            link[0] = lt;
            link[1] = rt;
            level = lv;
        }

        ~BNode() {

        }
    };

    class BST {
        private:
            std::vector<std::string> sortOrder;
            BNode * root;
            BNode * nullNode;
            std::filebuf * file;
        public:
            BST( );
            BST( const BST & rhs );
            ~BST( );
            void setFile(std::fstream & inFile) { file = inFile.rdbuf(); };
            void setComp(std::vector<std::string> order) { sortOrder = order; };
            bool isEmpty() const;
            void makeEmpty() ;
            void inorderTree( ) const {
                if (!( root == nullNode ))
       //             cout << "Empty tree" << endl;
         //       else
                    inorderTree( root );
            }
            void insert( const BNode::Comparable & x )
            {
                insert( x, root );
            }
            void remove( const BNode::Comparable & x )
            {
                remove( x, root );
            }
            int height() const;

            const BNode::Comparable  findMin( ) const
            {
                if( isEmpty( ) ) {
                    BNode::Comparable nulo;
                    nulo.fileLine = "NaN";
                    return nulo;
                }
                BNode *ptr = root;
                while( ptr->link[0] != nullNode )
                    ptr = ptr->link[0];

                return ptr->element;
            }


        private:
            void insert( const BNode::Comparable & x, BNode * & t );
            void remove( const BNode::Comparable & x, BNode * & t );
            bool compare(const BNode::Comparable lt, const BNode::Comparable rt);
            bool igual(const BNode::Comparable lt, const BNode::Comparable rt);
            bool desigual(const BNode::Comparable lt, const BNode::Comparable rt) {
                return !igual( lt, rt);
            }
            void skew( BNode * & t );
            void split( BNode * & t );
            void rotateWithLeftChild( BNode * & k2 );
            void rotateWithRightChild( BNode * & k1 );
            void inorderTree(BNode *t) const;
            int height(BNode* const &ptr) const ;
            void makeEmpty( BNode * & t );
            BNode * clone( BNode *t ) const
            {
                if( t == t->link[0] )  // Cannot test against nullNode!!!
                    return nullNode;
                else
                    return new BNode( t->element, clone( t->link[0] ), clone( t->link[1] ), t->level );
            }


    };

}

#endif // BST_H_INCLUDED
